import collections


# class MinStack(object):
#
#     def __init__(self):
#         self.stack = collections.deque()
#         self.order = collections.deque()
#
#     def push(self, val):
#         """
#         :type val: int
#         :rtype: None
#         """
#         self.stack.append(val)
#         for i in range(len(self.order)):
#             if val < self.order[i]:
#                 self.order.insert(i, val)
#                 break
#         if not self.order:
#             self.order.append(val)
#         else:
#             if val >= self.order[-1]:
#                 self.order.append(val)
#     def pop(self):
#         """
#         :rtype: None
#         """
#         node = self.stack.pop()
#         self.order.remove(node)
#
#     def top(self):
#         """
#         :rtype: int
#         """
#         return self.stack[-1]
#
#     def getMin(self):
#         """
#         :rtype: int
#         """
#         return self.order[0]

# class MinStack(object):
#
#     def __init__(self):
#         self.stack = collections.deque()
#         self.minStack = collections.deque([float('inf')])
#
#     def push(self, val):
#         """
#         :type val: int
#         :rtype: None
#         """
#         self.stack.append(val)
#         self.minStack.append(min(val, self.minStack[-1]))
#     def pop(self):
#         """
#         :rtype: None
#         """
#         self.stack.pop()
#         self.minStack.pop()
#
#     def top(self):
#         """
#         :rtype: int
#         """
#         return self.stack[-1]
#
#     def getMin(self):
#         """
#         :rtype: int
#         """
#         return self.minStack[-1]

# 不适用辅助栈
class MinStack(object):

    def __init__(self):
        self.stack = collections.deque()

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        if not self.stack:
            self.stack.append(0)
            self.min_value = val
        else:
            diff = val - self.min_value
            if diff >= 0:
                self.stack.append(diff)
            else:
                self.stack.append(val - self.min_value)
                self.min_value = val

    def pop(self):
        """
        :rtype: None
        """
        val = self.stack.pop()
        if val >= 0:
            return self.min_value + val
        else:
            return_val = self.min_value
            self.min_value = self.min_value - val
            return return_val

    def top(self):
        """
        :rtype: int
        """
        if self.stack[-1] >= 0:
            return self.min_value + self.stack[-1]
        else:
            return self.min_value

    def getMin(self):
        """
        :rtype: int
        """
        return self.min_value


obj = MinStack()
obj.push(-2)
obj.push(0)
obj.push(-3)
print(obj.getMin())
obj.pop()
print(obj.top())
print(obj.getMin())
